﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using TestGraph.Interfaces;

namespace TestGraph
{
    public class BasicGraph : IBasicGraph
    {
        private List<Vertex> _vertices;

        public BasicGraph()
        {
            _vertices = new List<Vertex>();
        }

        #region Private Methods

        private void UnMark()
        {
            foreach (Vertex n in _vertices)
            {
                n.Marked = false;
            } // end foreach
        }

        private Vertex GetNextUnmarked(List<Vertex> list)
        {
            int size = 0;
            Vertex v = null;
            bool found = false;
            while (!found && size < list.Count)
            {
                if (!list[size++].Marked)
                {
                    found = true;
                    v = list[size - 1];
                }

            } // end while
            return v;
        }

        private Edge FindEdge(Vertex from, Vertex to)
        {
            Edge result = null;
            int size = -1;
            bool found = false;
            while (!found && ++size < from.Edges.Count)
            {
                if (from.Edges[size].To.Equals(to))
                {
                    result = from.Edges[size];
                    found = true;
                } // end if
            } // end while
            return result;
        }

        #endregion

        #region Public Methods

        public void AddVertex(Vertex vertex)
        {
            _vertices.Add(vertex);
        }

        public void AddEdge(Vertex from, Vertex to)
        {
            from.Edges.Add(new Edge(from, to));
        }

        public void RemoveVertex(Vertex vertex)
        {
            _vertices.Remove(vertex);
        }

        public void RemoveEdge(Vertex from, Vertex to)
        {
            int index = -1;
            bool done = false;
            while (!done && ++index < from.Edges.Count)
            {
                if (from.Edges[index].To.Equals(to))
                {
                    from.Edges.Remove(from.Edges[index]);
                    done = true;
                } // end if
            } // end while
        }

        public bool ContainsVertex(Vertex vertex)
        {
            int index = -1;
            bool found = false;
            while (!found && ++index < _vertices.Count)
            {
                if (_vertices[index].Equals(vertex))
                {
                    found = true;
                } // end if
            } // end while

            return found;
        }

        public bool IsAdjacent(Vertex from, Vertex to)
        {
            int index = -1;
            bool isAdjacent = false;
            while (!isAdjacent && ++index < from.Edges.Count)
            {
                if (from.Edges[index].To.Equals(to))
                {
                    isAdjacent = true;
                } // end if
            } // end while

            return isAdjacent;
        }

        public IList GetAdjacencies(Vertex vertex)
        {
            List<Vertex> adjacencies = new List<Vertex>();
            foreach (Edge e in vertex.Edges)
            {
                adjacencies.Add(e.To);
            } // end foreach

            return adjacencies;
        }

        public IEnumerator Vertices()
        {
            return _vertices.GetEnumerator();
        }

        public IEnumerator Edges()
        {
            List<Edge> allEdges = new List<Edge>();
            foreach (Vertex v in _vertices)
            {
                allEdges.AddRange(v.Edges);
            } // end foreach

            return allEdges.GetEnumerator();
        }

        public bool IsEmpty()
        {
            return _vertices.Count == 0;
        }

        public int GetNoOfVertices()
        {
            return _vertices.Count;
        }

        public int GetNoOfEdges()
        {
            List<Edge> allEdges = new List<Edge>();
            foreach (Vertex v in _vertices)
            {
                allEdges.AddRange(v.Edges);
            } // end foreach

            return allEdges.Count;
        }

        public void Clear()
        {
            _vertices = new List<Vertex>();
        }

        #endregion

        #region Traversals (from interface)

        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a depth-first search: Iterative version
        /// </summary>
        public IList DfsIterative(Vertex vertex)
        {
            List<Vertex> result = new List<Vertex>();
            Stack<Vertex> s = new Stack<Vertex>();
            result.Add(vertex);
            s.Push(vertex);
            vertex.Marked = true;

            while (s.Count > 0)
            {
                Vertex v = GetNextUnmarked((List<Vertex>)GetAdjacencies(s.Peek()));
                if (v == null) // no unvisited vertices adjacent
                {
                    s.Pop(); // backtrack
                }
                else
                {
                    result.Add(v);
                    s.Push(v);
                    v.Marked = true;
                } // end if else
            } // end while
            UnMark();
            return result;
        }

        List<Vertex> dfsrResult = new List<Vertex>();
        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a depth-first search: Recursive version
        /// </summary>
        public IList DfsRecursive(Vertex vertex)
        {
            try
            {
                vertex.Marked = true;
                dfsrResult.Add(vertex);

                foreach (Vertex v in GetAdjacencies(vertex))
                {
                    if (!v.Marked) // else backtrack
                    {
                        DfsRecursive(v);
                    } // end if
                }// end foreach

                return dfsrResult;
            }
            finally
            {
                UnMark();
            }
        }

        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a breadth-first search: Iterative version
        /// </summary>
        public IList BfsIterative(Vertex vertex)
        {
            List<Vertex> result = new List<Vertex>();
            Queue<Vertex> q = new Queue<Vertex>();
            result.Add(vertex);
            q.Enqueue(vertex);
            vertex.Marked = true;

            while (q.Count > 0)
            {
                foreach (Vertex v in GetAdjacencies(q.Dequeue()))
                {
                    if (!v.Marked)
                    {
                        result.Add(v);
                        q.Enqueue(v);
                    }
                }
            }
            UnMark();
            return result;
        }

        #endregion
    }
}
